using System.Text;

namespace array_demo.Model
{
    public class SortArray1<Key> where Key : IComparable<Key>
    {
        private Key[] keys;
        private int N;
        public SortArray1(int capacity)
        {
            keys = new Key[capacity];
        }

        public SortArray1() : this(10) { }

        public int Count { get { return N; } }

        public bool IsEmpty { get { return N == 0; } }

        /// <summary>
        /// 二分查找法确定是否存在 
        /// </summary>
        /// <param name="key"></param>
        /// <returns></returns>
        public int Rank(Key key)
        {
            int l = 0;
            int r = N - 1;

            while (l <= r)
            {
                int mid = l + (r - l) / 2;
                if (l.CompareTo(keys[mid]) < 0)
                    r = mid - 1;
                else if (l.CompareTo(keys[mid]) > 0)
                    r = mid + 1;
                else
                    //  如果存在就直接返回索引
                    return mid;
            }
            // 不存在就返回l；
            return l;
        }

        /// <summary>
        /// 新增元素
        /// </summary>
        /// <param name="key"></param>
        public void Add(Key key)
        {
            int i = Rank(key);

            if (N == keys.Length)
                ResetCapacity(2 * keys.Length);

            if (i < N && keys[i].CompareTo(key) == 0)
                return;  //相等时不需要新增

            for (int j = N - 1; j >= i; j--)
            {
                keys[j + 1] = keys[j];
            }
            keys[i] = key;
            N++;
        }

        /// <summary>
        /// 删除元素
        /// </summary>
        /// <param name="key"></param>
        public void Remove(Key key)
        {
            if (IsEmpty)
                return;
            int i = Rank(key);
            if (i == N && keys[i].CompareTo(key) == 0)
                return;
            for (int j = i + 1; j <= N - 1; j++)
            {
                keys[j - 1] = keys[j];
            }
            N--;
            keys[N] = default(Key);
            if (N == keys.Length / 4)
            {
                ResetCapacity(keys.Length / 2);
            }
        }

        /// <summary>
        /// 获取最小值 
        /// </summary>
        /// <returns></returns>
        public Key Min()
        {
            if (IsEmpty)
                throw new ArgumentException("索引为空");
            return keys[0];
        }

        public Key Max()
        {
            if (IsEmpty)
                throw new ArgumentException("索引为空");
            return keys[N - 1];
        }

        /// <summary>
        /// 查询排名为k的键值
        /// </summary>
        /// <param name="k"></param>
        /// <returns></returns>
        public Key Select(int k)
        {
            if (IsEmpty)
                throw new ArgumentException("索引为空");
            if (k < 0 && k >= N)
                throw new ArgumentException("索引溢出");
            return keys[k];
        }

        public bool Contains(Key key)
        {
            int i = Rank(key);
            if (i < N && keys[i].CompareTo(key) == 0)
                return true;
            return false;
        }

        /// <summary>
        /// 小于或等于key的最大键
        /// </summary>
        /// <param name="key"></param>
        /// <returns></returns>
        public Key Floor(Key key)
        {
            int i = Rank(key);
            if (i < N && keys[i].CompareTo(key) == 0)
                return keys[i];
            if (i == 0)
                throw new AggregateException("没有找到小于或等于key的最大键");
            else
                return keys[i - 1];
        }

        /// <summary>
        /// 找到大于或等于key的最小键
        /// </summary>
        /// <param name="key"></param>
        /// <returns></returns>
        public Key Ceiling(Key key)
        {
            int i = Rank(key);
            if (i < N && keys[i].CompareTo(key) == 0)
                return keys[i];
            if (i == N)
                throw new AggregateException("没有找到小于或等于key的最大键");
            else
                return keys[i];
        }

        /// <summary>
        /// 容量扩充
        /// </summary>
        /// <param name="newCapacity"></param>
        private void ResetCapacity(int newCapacity)
        {
            Key[] newData = new Key[newCapacity];
            for (int i = 0; i < N; i++)
            {
                newData[i] = keys[i];
            }
            keys = newData;
        }

        /// <summary>
        /// 重写转字符串
        /// </summary>
        /// <returns></returns>
        public override string ToString()
        {
            StringBuilder stringBuilder = new StringBuilder();
            // stringBuilder.Append(string.Format("Array1: count:{0} capacity ={1}\n", N, data.Length));
            stringBuilder.Append("[");
            for (int i = 0; i < N; i++)
            {
                stringBuilder.Append(keys[i]);
                if (i != N - 1)
                {
                    stringBuilder.Append(",");
                }
            }
            stringBuilder.Append("]");
            return stringBuilder.ToString();
        }
    }
}